#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 062. 不同路径.py
@time: 2022/1/28 17:15
@desc: https://leetcode-cn.com/problems/unique-paths/
> 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

@解题思路：
    1. 动态规划
    2. Ot(mn), Os(mn)
'''
class Solution(object):
    # 超时
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        self.ans = 0
        def dfs(i, j):
            if i==m-1 and j==n-1:
                self.ans += 1
                return
            if i==m or j==n: return
            dfs(i+1, j)
            dfs(i, j+1)
        dfs(0, 0)
        return self.ans

class Solution2(object):
    # dp
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[0]*n for _ in range(m)]
        for i in range(n): dp[0][i] = 1
        for i in range(m): dp[i][0] = 1
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]
if __name__ == '__main__':
    RES = Solution().uniquePaths(3, 7)
    print(RES)
